package Offer.offer2019;

import domain.ListNode;

/**
 * 链表的倒数第K个结点
 *
 * @author: leiwenkang02@meituan.com
 * @date: 2019/4/27
 * @time: 20:55
 */
public class Offer15 {
    public ListNode getLastK(ListNode head, int k) {
        if (head == null || k <= 0) {
            throw new RuntimeException("非法输入");
        }

        ListNode p1 = head;
        ListNode p2 = head;

        //p1先走k步
        for (int i = 0; i < k; i++) {
            if (p1.next != null) {
                p1 = p1.next;
            } else {
                return null;
            }

        }

        //p1和p2同时走，直到p1走到最后结点，此时p2刚好指向倒数第k个结点
        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p2;
    }
}
